//
// Created by madison on 2022/7/9.
//

#include "string"
#include "vector"

using namespace std;

class Solution {
public:
    // 方法一：横向扫描
    string longestCommonPrefix(vector<string> &strs) {
        if (!strs.size()) {
            return "";
        }
        string prefix = strs[0];
        int count = strs.size();
        for (int i = 0; i < count; ++i) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (!prefix.size()) {
                break;
            }
        }
        return prefix;
    }

    string longestCommonPrefix(const string &str1, const string &str2) {
        int length = min(str1.size(), str2.size());
        int index = 0;
        while (index < length && str1[index] == str2[index]) {
            ++index;
        }
        return str1.substr(0, index);
    }

    // 方法二：纵向扫描
    string longestCommonPrefix1(vector<string> &strs) {
        if (!strs.size()) {
            return "";
        }
        int length = strs[0].size();
        int count = strs.size();
        for (int i = 0; i < length; ++i) {
            char c = strs[0][i];
            for (int j = 0; j < count; ++j) {
                if (i == strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

int main() {
    Solution solution;
    vector<string> strs = {"flower", "flow", "flight"};
    printf("%s", solution.longestCommonPrefix(strs).c_str());
    return 0;
}